// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort - list/
public class Code06_SortList {
    // 不要提交这个类，这是内部辅助类，用于表示链表节点
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 提交如下的方法
    // 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
    // 注意为了额外空间复杂度O(1)，所以不能使用递归
    // 因为mergeSort递归需要O(log n)的额外空间
    public static ListNode sortList(ListNode head) {
        // 计算链表的长度
        int n = 0;
        ListNode cur = head;
        while (cur!= null) {
            n++;
            cur = cur.next;
        }

        // l1...r1 每组的左部分
        // l2...r2 每组的右部分
        // next 下一组的开头
        // lastTeamEnd 上一组的结尾
        ListNode l1, r1, l2, r2, next, lastTeamEnd;

        // 外层循环控制分组的大小，每次分组大小翻倍
        for (int step = 1; step < n; step <<= 1) {
            // 第一组很特殊，因为要决定整个链表的头，所以单独处理
            l1 = head;
            // 找到第一组左部分的结尾r1，包含l1在内往下数step个节点
            r1 = findEnd(l1, step);
            // 确定右部分的开头l2
            l2 = r1.next;
            // 找到右部分的结尾r2，包含l2在内往下数step个节点
            r2 = findEnd(l2, step);
            // 记录下一组的开头
            next = r2.next;
            // 将第一组左部分和右部分断开
            r1.next = null;
            r2.next = null;
            // 合并第一组的左右两部分
            merge(l1, r1, l2, r2);
            // 更新链表头为合并后的头
            head = start;
            // 记录第一组合并后的结尾作为上一组的结尾
            lastTeamEnd = end;

            // 处理后续的组
            while (next != null) {
                // 确定下一组的左部分
                l1 = next;
                // 找到下一组左部分的结尾r1，包含l1在内往下数step个节点
                r1 = findEnd(l1, step);
                // 确定下一组右部分的开头l2
                l2 = r1.next;
                // 如果右部分为空，直接将左部分连接到上一组结尾后面并跳出循环
                if (l2 == null) {
                    lastTeamEnd.next = l1;
                    break;
                }
                // 找到下一组右部分的结尾r2，包含l2在内往下数step个节点
                r2 = findEnd(l2, step);
                // 记录再下一组的开头
                next = r2.next;
                // 将下一组左部分和右部分断开
                r1.next = null;
                r2.next = null;
                // 合并下一组的左右两部分
                merge(l1, r1, l2, r2);
                // 将合并后的部分连接到上一组结尾后面
                lastTeamEnd.next = start;
                // 更新上一组结尾为合并后的结尾
                lastTeamEnd = end;
            }
        }
        return head;
    }

    // 包括s在内，往下数k个节点返回
    // 如果不够，返回最后一个数到的非空节点
    public static ListNode findEnd(ListNode s, int k) {
        // 循环往下找节点，直到找到k个节点或者到达链表末尾
        while (s.next!= null && --k!= 0) {
            s = s.next;
        }
        return s;
    }

    public static ListNode start;
    public static ListNode end;

    // l1...r1 -> null : 有序的左部分
    // l2...r2 -> null : 有序的右部分
    // 整体merge在一起，保证有序
    // 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
    public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
        ListNode pre;
        // 比较左右两部分的第一个节点的值，确定合并后链表的头
        if (l1.val <= l2.val) {
            start = l1;
            pre = l1;
            l1 = l1.next;
        } else {
            start = l2;
            pre = l2;
            l2 = l2.next;
        }

        // 依次比较左右两部分剩余节点的值，将较小值的节点连接到pre后面
        while (l1!= null && l2!= null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                pre = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                pre = l2;
                l2 = l2.next;
            }
        }

        // 如果左部分还有剩余节点，将其连接到pre后面，并设置end为r1
        if (l1!= null) {
            pre.next = l1;
            end = r1;
        } else {
            // 如果右部分还有剩余节点，将其连接到pre后面，并设置end为r2
            pre.next = l2;
            end = r2;
        }
    }
}